package leetcode_2001_2100;

import java.util.*;

public class LeeCode_2065 {
    public static void main(String[] args) {

        System.out.println(maximalPathQuality(new int[]{5,0,1}, new int[][]{{0,1,10},{0,2,26},{1,2,10}}, 40));
        System.out.println(maximalPathQuality(new int[]{0,1,2}, new int[][]{{1,2,10}}, 10));
        System.out.println(maximalPathQuality(new int[]{0,32,10,43}, new int[][]{{0,1,10},{1,2,15},{0,3,10}}, 49));
        System.out.println(maximalPathQuality(new int[]{1,2,3,4}, new int[][]{{0,1,10},{1,2,11},{2,3,12},{1,3,13}}, 50));
    }
    private static int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1], val = edge[2];
            if (map.containsKey(x)){
                map.get(x).add(new int[]{y, val});
            }else {
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{y, val});
                map.put(x, list);
            }
            if (map.containsKey(y)){
                map.get(y).add(new int[]{x, val});
            }else {
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{x, val});
                map.put(y, list);
            }
        }
        int[] ans = new int[]{values[0]};
        if (!map.containsKey(0))
            return values[0];
        int[] shortest = new int[values.length];
        Arrays.fill(shortest, 100_0000);
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        queue.add(new int[]{0, 0});
        shortest[0] = 0;
        while (!queue.isEmpty()){
            int[] p = queue.poll();
            int now = p[0], dis = p[1];
            List<int[]> next = map.get(now);
            for (int[] node : next) {
                int j = node[0], cost = node[1];
                if (dis + cost < shortest[j]){
                    shortest[j] = dis + cost;
                    queue.add(new int[]{j, shortest[j]});
                }
            }
        }
        int start = values[0];
        values[0] = 0;
        dfs(map, shortest, values, 0, 0, start, ans, maxTime);
        return ans[0];
    }
    private static void dfs(Map<Integer, List<int[]>> map, int[] shortest, int[] values, int now, int dis, int get, int[] ans, int maxTime){
        if (shortest[now] + dis > maxTime)
            return;
        if (now == 0){
            ans[0] = Math.max(ans[0], get);
        }
        if (!map.containsKey(now))
            return;
        List<int[]> list = map.get(now);
        for (int[] nextNode : list) {
            int next = nextNode[0], cost = nextNode[1];
            int value = values[next];
            values[next] = 0;
            dfs(map, shortest, values, next, dis + cost, get + value, ans, maxTime);
            values[next] = value;
        }
    }
}
